/**
 * describe:
 *
 * @author chaP
 * @date 2019/04/07
 */
package CodingTest.AC20190407;

/**
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

 注意:

 每个数组中的元素不会超过 100
 数组的大小不会超过 200
 示例 1:

 输入: [1, 5, 11, 5]

 输出: true

 解释: 数组可以分割成 [1, 5, 5] 和 [11].


 示例 2:

 输入: [1, 2, 3, 5]

 输出: false

 解释: 数组不能分割成两个元素和相等的子集.
 */
public class canPartition {
    //递归法：超时
    public boolean canPartition(int[] nums){
        int sum = 0;
        for(int i = 0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2 == 1) return false;
        int midsum  = sum/2;
        return  helper(nums,midsum,0);
    }
    public boolean helper(int[] nums ,int sum,int index){
        if(sum == 0)
            return true;
        if(sum <0 || index >=nums.length-1)
            return false;
         return helper(nums,sum-nums[index],index+1)||
                    helper(nums,sum,index+1);
    }
    ///////////////////////////////////////////////////////
    //动态规划
    public boolean canPartition1(int[] nums){
       int sum  = 0;
       for(int k:nums)
           sum+=k;
       if(sum%2==1) return false;
       return helper(nums,sum/2);
    }
    public boolean helper(int[] nums,int sum){
         return true;
    }

    public static void main(String[] args) {
        canPartition cp = new canPartition();
        int[] nums = {1, 5, 11, 5};
        System.out.println(cp.canPartition1(nums));
    }

}
